/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-15 09:45:09
 * @LastEditors: lily
 * @LastEditTime: 2021-04-15 11:04:09
 */
/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
//  思路：
//  找出非降序对（即两边的柱子），计算雨水量，但最大值出现后的部分将不计算，因此再逆序计算一次，防止重复，逆序计算只计算升序对
//  官方双指针法：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/

//  复杂度：O(n) O(1)


var trap = function (height) {
    // 去掉首尾的0，无效数据
    while (height[0] === 0) {
        height.shift()
    }
    while (height[height.length - 1] === 0) {
        height.pop()
    }
    // 正序 找出非降序对，逐段计算雨水
    let len = height.length, start = 0, end = 0, sum = 0
    while (end < len) {
        if (end > start) {
            if (height[end] >= height[start]) {
                for (let i = start; i < end; i++) {
                    sum += height[start] - height[i]
                }
                start = end
            }
        }
        end++
    }

    // 逆序 找出升序对（防止重复计算），逐段计算雨水
    height.reverse()
    start = 0, end = 0
    while (end < len) {
        if (end > start) {
            if (height[end] > height[start]) {
                for (let i = start; i < end; i++) {
                    sum += height[start] - height[i]
                }
                start = end
            }
        }
        end++
    }
    return sum
};
// @lc code=end

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));